package com.simon.study.algorithm.tree;

import static com.simon.study.algorithm.tree.RBTree.adjustAfterRotate;
import com.simon.study.algorithm.tree.TNode.RBNode;

/**
 * <p>
 *
 * @author simon
 */
public class RBTree2 {
    RBNode      root;
    int         size;



    public RBNode leftRotate(RBNode spot){
        RBNode node = (RBNode) AVLTree.leftRotate(spot);

        adjustAfterRotate(spot, node);

        if( spot.right  != null ){ spot.right.parent = spot; }
        if( root == spot ){ root = node; }
        return node;
    }

    public RBNode rightRotate(RBNode spot){
        RBNode node = (RBNode) AVLTree.rightRotate(spot);

        adjustAfterRotate(spot, node);

        if( spot.left != null ){ spot.left.parent = spot; }
        if( root == spot ){ root = node; }

        return node;
    }


    public RBNode clear(){
        RBNode node = root;
        root = null; size = 0;
        return node;
    }

    public static void main(String[] args) {
        RBTree2 brtree = new RBTree2();
        int[] arr = new int[]{55,66,44,33,11,22,88,99,30,38,28,62};

        brtree.clear();

        brtree.add(3);
        for (int i = 0; i < arr.length; i++) {
            brtree.add(arr[i]);
        }
    }

    public RBNode add(int data){
        root = add(root, data);
        if( size == 1){ root.color = RBNode.BLACK; }
        return root;
    }

    public RBNode add(RBNode node, int data){
        if(node == null){ size++; return new RBNode(data, RBNode.RED); }
        if(data <= node.data){
            node.setLeft( add((RBNode) node.left, data) );
        } else{
            node.setRight( add((RBNode) node.right, data));
        }

        if(isRed((RBNode) node.right) && !isRed((RBNode) node.left)){
            node = leftRotate(node);
        }
        if(isRed((RBNode) node.left) && isRed((RBNode) node.left.left)){
            node = rightRotate(node);
        }
        if(isRed((RBNode) node.left) && isRed((RBNode) node.right)){
            flipColor(node);
        }
        return node;
    }

    public static void flipColor(RBNode node){
        node.color = RBNode.RED;
        ((RBNode)node.left).color  = RBNode.BLACK;
        ((RBNode)node.right).color = RBNode.BLACK;
    }


    public boolean isRed(RBNode node){
        if(node != null && node.color == RBNode.RED){ return true; }
        return false;
    }
}
